package org.czl.gh;

import java.util.HashMap;

public class l2584 {
    public static void main(String[] args) {
        //[4,7,8,15,3,5]
        System.out.println(findValidSplit(new int[]{4, 7, 8, 15, 3, 5}));
    }
    //2个数gcd为1表示 2个数不能有公共的质因子
    static int findValidSplit(int[] nums) {
        HashMap<Integer, Integer> left = new HashMap<Integer, Integer>();
        int n = nums.length;
        int[] right = new int[n + 1];
        for(int i = 0; i < n; i++){
            int ret = nums[i];
            for(int j = 2; j * j <= ret; j++){
                if(ret % j == 0){
                    if(left.containsKey(j)){
                        right[left.get(j)] = i;
                    }else{
                        left.put(j,i);
                    }
                    while(ret % j == 0){
                        ret /= j;
                    }
                }
            }
            if(ret > 1){
                if(left.containsKey(ret)){
                    right[left.get(ret)] = i;
                }else{
                    left.put(ret,i);
                }
            }
        }
        int l = 0; int maxR = 0;
        for(; l < n; l++){
            if(l > maxR){
                return maxR;
            }
            maxR = Math.max(maxR, right[l]);
        }
        return -1;
    }
}
